package leetcode.数组;

import java.util.ArrayList;
import java.util.List;

/**
 * 螺旋矩阵
 * <p>
 * 剑指offer 第29题顺时针打印矩阵
 */
public class Test54螺旋矩阵 {

    public static List<Integer> spiralOrder(int[][] nums) {
        List<Integer> ans = new ArrayList<>();
        if (nums.length == 0)
            return ans;
        int top = 0;
        int bottom = nums.length - 1;
        int left = 0;
        int right = nums[0].length - 1;
        while (true) {
            // 行不动，从左往右遍历列
            for (int i = left; i <= right; i++)
                ans.add(nums[top][i]);
            top++;// 顺时针转到下面
            if (left > right || top > bottom)
                break;

            // 列不动，往下遍历行
            for (int i = top; i <= bottom; i++)
                ans.add(nums[i][right]);
            right--;// 顺时针向左边转
            if (left > right || top > bottom)
                break;

            // 行不动，从右往左遍历列
            for (int i = right; i >= left; i--)
                ans.add(nums[bottom][i]);
            bottom--;// 顺时针往上走
            if (left > right || top > bottom)
                break;

            // 列不动，往上遍历
            for (int i = bottom; i >= top; i--)
                ans.add(nums[i][left]);
            left++; // 顺时针往右转
            if (left > right || top > bottom)
                break;
        }
        return ans;
    }

    public static void main(String[] args) {
//        int[][] nums = {
//                {1, 2, 3},
//                {4, 5, 6},
//                {7, 8, 9}
//        };
        int[][] nums = {
                {1, 2, 3, 33},
                {4, 5, 6, 66},
                {7, 8, 9, 99}
        };
        System.out.println(spiralOrder(nums));
        System.out.println(spiralOrder2(nums));
    }

    public static List<Integer> spiralOrder2(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        if (matrix.length == 0)
            return ans;
        int row = matrix.length;
        int col = matrix[0].length;
        int layers = (Math.min(row, col) - 1) / 2 + 1;
        for (int i = 0; i < layers; i++) {
            // 从左到右
            for (int j = i; j < col - i; j++) {
                ans.add(matrix[i][j]);
            }
            // 从右上到右下
            for (int j = i + 1; j < row - i; j++) {
                ans.add(matrix[j][col - 1 - i]);
            }
            // 从右到左
            // 只有一层或者只有一列的时候，或者旋转到内层之后只有单独的一列或者一行的时候
            // 是不需要执行下面这两个for循环的，所以要检测一下：当前的行号（列号）是否等于层数
            for (int j = col - i - 2; j >= i && (row - i - 1 != i); j--) {
                ans.add(matrix[row - i - 1][j]);
            }
            // 从左下到左上
            for (int j = row - i - 2; j > i && (col - i - 1 != i); j--) {
                ans.add(matrix[j][i]);
            }
        }
        return ans;
    }
}
